main = do
  putStrLn "Primitive Einheitswurzeln:"
  putStrLn $ show $ map head find_pur_17_8
  putStrLn "Potenzen:"
  putStrLn $ concat $ map (\x -> show x ++ "\n") find_pur_17_8

  putStrLn "D:"
  putStrLn $ concat $ map (\x -> show x ++ "\n") matrix_17_8

  putStrLn "D^-1:"
  putStrLn $ concat $ map (\x -> show x ++ "\n") inverseMatrix_17_8

---------------------- Field ------

-- multiply in Z_prime
mulp prime a b = mod (a*b) prime 
-- add in Z_prime
addp prime a b = mod (a+b) prime 
-- inverse of a in field Z_prim
invp prime a = head $ dropWhile (\y -> mulp prime a y /= 1) [1..prime-1]
-- potence in Z_prim
potp prime a b = (iterate (mulp prime a) 1)!!b

---------------------- END Field --

-- set of potences of x
uniquePotences prime x = (takeWhile (\a -> not $ a == 1) $ map (\y -> potp prime x y) [1..]) ++ [1]
-- find primitive k-th unit root
find_pur prime k = filter (\x -> length x == k) $ map (uniquePotences prime) [1..(prime-1)]

-- dft matrix over Z_prim and a given prime k-th unitroot
buildMatrix prime primroot k = splitEvery k $ rootlist where
  rootlist = map (potp prime primroot) potlist
  potlist = [i*j | i <- [0..k-1], j <- [0..k-1]]

-- multiply a matrix with a factor in Z_prime
multMatrix prime n m = matrixmap (\x -> mulp prime n x) m

matrixmap :: (a -> b) -> [[a]] -> [[b]]
matrixmap f m = map (map f) m

find_pur_17_8 = find_pur 17 8
matrix_17_8 = buildMatrix 17 2 8
inverseMatrix_17_8 = multMatrix 17 (invp 17 8) $ buildMatrix 17 9 8

---------------------- Helper ------

-- slitt list into 2d matrix
splitEvery :: Int -> [a] -> [[a]]
splitEvery n l = let (a,b) = splitAt n l in 
  case a of
    [] -> case b of
          [] -> []
          _  -> [b]
    _  -> a : (splitEvery n b)

---------------------- END Helper --